package array

/*
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素

输入: [1,3,5,6], 5
输出: 2

输入: [1,3,5,6], 2
输出: 1

思路：有序数组即可二分查找
*/
import "fmt"

func SearchInsertByMyself(nums []int, target int) int {
	if len(nums) == 0 {
		return 0
	}

	length := len(nums)

	if target > nums[length-1] {
		return length
	}

	if target <= nums[0] {
		return 0
	}

	if target == nums[length-1] {
		return length - 1
	}

	left := 0
	right := length - 1

	for left < right {
		center := int((left + right) / 2)
		if nums[center] == target {
			return center
		} else if nums[center] > target {
			right = center - 1
		} else if nums[center] < target {
			left = center + 1
		}
	}

	fmt.Println(left, right)

	if left == 0 && target > nums[0] {
		return left + 1
	}
	if nums[left] < target && target < nums[left+1] {
		return left + 1
	}

	return left
}

func SearchInsert(nums []int, target int) int {
	n := len(nums)
	left, right := 0, n-1
	ans := n
	for left <= right {
		// mid := (right-left)>>1 + left
		mid := int((right + left) / 2)
		if target <= nums[mid] {
			ans = mid // target在(left,right]才保存
			right = mid - 1
		} else { // 要么target在(left,right]左侧，要么还在区间内
			left = mid + 1
		}
	}
	return ans
}
